#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "rb_tree.h"

void add_node(rb_root_t *root, rb_node_t *new)
{
	rb_node_t **p = NULL;
	rb_node_t *parent = NULL;

	p = &(root->node);
	while(*p) {
		parent = *p;
		if (new->data < parent->data)
			p = &(*p)->rb_left;
		else if (new->data > parent->data)
			p = &(*p)->rb_right;
		else
			printf("node %d already in tree\n", new->data);
	}
	rb_link_node(new, parent, p);
	rb_set_red(new);
	rb_insert_color(new, root);
}

void delete_node(rb_root_t *root, int data)
{
	rb_node_t *p = NULL;

	p = root->node;
	while(p) {
		if (data < p->data)
			p = p->rb_left;
		else if (data > p->data)
			p = p->rb_right;
		else 
			break;
	}
	if (p)
		rb_erase(p, root);
}

void print_test(rb_root_t *root)
{
	rb_node_t *p;

	p = rb_first(root);
	while(p != NULL) {
		printf("id:%d:color:%d \n", p->data, p->color);
		p = rb_next(p);
	}
}

int test_tree(rb_root_t *root)
{
	int data[] = {6, 5, 4, 3, 2, 1};
	//int data[] = {1, 2, 3, 4, 5, 6};
	//int data[] = {1, 2, 3, 4, 5, 6, 19, 18, 17, 16, 15, 14, 13, 12, 11, 21, 50, 25, 45, 30, 40, 31, 39, 32, 38, 33, 37};
	int n, i, ret = 0;
	rb_node_t *node = NULL;

	n = sizeof(data) / sizeof(int);
	
	for (i = 0; i < n; i++) {
		//printf("i:%d:data:%d \n", i, data[i]);
		node = (rb_node_t *)malloc(sizeof(rb_node_t));
		if (!node) {
			ret = -1;
			break;
		}
		memset(node, 0, sizeof(rb_node_t));
		node->data = data[i];
		add_node(root, node);
	}
	print_test(root);

	for (i = 0; i < n; i++) {
		delete_node(root, data[i]);
		printf("\n");
		print_test(root);
	}
	return ret;

}

void test_rb_tree(void) {
	rb_root_t root[1];
	int ret = 0;

	root->node = NULL;	
	ret = test_tree(root);
	if (ret < 0) {
		printf("create tree failed\n");
	}

	return;
}

int main(void)
{
	test_rb_tree();
	return 0;
}

